本发明解决按照二维坐标值快速在大量二维点数据中完成其对应点对象的查询与匹配问题,提供一种批量二维点数据中坐标快速匹配的方法,本方法首先对所有的二维点数据进行复合结构组织:首先计算大量二维点集所在的包络矩形,继而按照固定的长、宽将其分解为规整排列的小矩形格网,继而将所有的二维点数据按照其空间坐标位置分别分配到这些小矩形格网中。在此基础上,设定根据二维坐标值进行点数据对象排序的规则,基于这种规则再对分配到每一个格网中的二维点集数据对象采用二叉树结构进行组织。在上述结构建立成功的基础上,即可实现二维坐标点的快速查询匹配,整个匹配检索过程可以做到基本与数据量无关。
1.批量二维点数据中坐标快速匹配的方法,包括对现存的大量二维点数据进行复合组织与坐标的快速匹配过程,具体步骤如下:步骤1:xa0对于现有的一批量二维坐标点数据,首先获取所有二维点数据所在的包络矩形:该包络矩形的两个边分别平行于坐标轴的X轴和Y轴,xa0其中X轴方向的最小值Xmin为所有点数据X坐标的最小值,X轴方向的最大值Xmax为所有点数据X坐标的最大值;同样的方法获得该包络矩形的Y轴方向的坐标范围(Ymin,Ymax),xa0如此得到能够包围所有二维点数据的包络矩形;步骤2:xa0将上述包络矩形沿X轴方向以及Y轴方向按照固定的长、宽进行格网分解,分解后的小格网长、宽设为上述包络矩形长和宽的1/5至1/100;xa0xa0xa0xa0xa0步骤3:xa0将所有的点坐标分配到每个格网中:即通过坐标计算获得每个二维点(x,y)“所属”的小格网,在每个小格网中存储其所“包含”的二维点的指针;采用下列计算公式即可计算其应该归附的小矩形格网的序列号:设X方向上的格网序号从0开始,沿X正方向;Y方向上的格网序号从0开始,沿Y正方向,则点坐标(x,y)所对应的格网序列号为:X_nxa0=xa0xa0[(x-Xmin)/Lx];xa0xa0Lx:xa0为矩形小格网的X方向上的长度;符号[xa0]表示去余取整运算;Y_n=xa0xa0[(y-Ymin)/Ly];xa0xa0xa0Ly:xa0为矩形小格网的Y方向上的长度;符号[xa0]表示去余取整运算;xa0xa0xa0xa0然后将当前二维点对象的指针保存到该小矩形网格(X_n,Y_n)的变量中,按照这种方法将所有二维点对象归附到其所对应的小格网中;步骤4:然后,设定二维点的排序准则,基于这种准则,对分配到每个小格网内的二维点集数据对象再采用二叉树结构进行组织;设定基于点坐标的排序方法:对于两个二维点,首先按照x坐标大小确定坐标点的“排序”;如果x坐标相同,则进一步按照xa0y坐标的大小确定坐标点的“排序”;如果y坐标也相同xa0,则认为该两点相同;至此完成对大量二维点数据的复合组织,该过程需要进行一次;步骤5:xa0在对现有的大批量二维点数据进行上述的复合组织后,根据任意二维点的坐标xa0(x₀,y₀)进行查询匹对,快速查找到该坐标对应的二维点对象:1)xa0首先,第一次匹配过程,根据其坐标数值(x₀,y₀)计算其对应的格网序号(X_nxa0,Y_n),确定其所在格网:X_nxa0=xa0xa0[(x₀-Xmin)/Lx];xa0xa0xa0xa0xa0Xmin:为包络矩形X方向的坐标最小值xa0xa0xa0Lx:xa0为小矩形格网的X方向上的长度;xa0xa0xa0符号[xa0]表示去余取整运算;Y_n=xa0xa0[(y₀-Ymin)/Ly];xa0xa0xa0xa0Ymin:为包络矩形Y方向的坐标最小值xa0xa0xa0xa0xa0Ly:xa0为矩形小格网的Y方向上的长度;xa0xa0xa0xa0符号[xa0]表示去余取整运算;2)xa0确定格网后,在该小格网中进行第二次匹配过程:通过当前的坐标数值(x₀,y₀),在以二叉数结构存储于该小格网内的二维点集对象中进行比对匹配搜索,快速得到该坐标所对应的实体二维点对象。
2.根据权利要求1所述的批量二维点数据中坐标快速匹配的方法,其中,步骤4中对每个小格网内的二维点集按设定排序准则进行二叉树进行组织,采用C++标准模板库中的set容器进行,该set容器实现了二叉树数据结构的组织算法。
3.根据权利要求2所述的批量二维点数据中坐标快速匹配的方法,其中,步骤5的第二次匹配时,直接调用set容器的搜索算法即获得对应的结果。技术领域:本发明涉及一种能够根据二维坐标快速在大批量二维点数据中匹配到其对应的二维点对象的方法。背景技术:目前随着空间信息科学的发展,xa0点坐标数据作为矢量数据的重要数据形式以及数据来源,在相关领域中受到越来越多的关注。在由其建立拓扑联系以及通过二维坐标点获取该坐标对应的点对象时,由于庞大的数据量,使得这一操作非常耗时,成为空间数据操作的瓶颈问题。发明目的:本发明解决了现有技术存在的上述问题,实现了按照二维坐标值快速在大批量二维点数据中完成其对应点对象的查询与匹配,本发明的方法能够大大缩短匹配过程,使其耗时基本与数据量无关。为实现以上目的,本发明采用以下描述方案:大批量二维点数据中坐标快速匹配的方法,包括对现存的大量二维点数据进行复合组织与坐标的快速匹配过程,具体步骤如下:步骤1:xa0对于现有的一批量二维坐标点数据,首先获取所有二维点数据所在的包络矩形:该包络矩形的两个边分别平行于坐标轴的X轴和Y轴,xa0其中X轴方向的最小值Xmin为所有点数据X坐标的最小值,X轴方向的最大值Xmax为所有点数据X坐标的最大值;同样的方法获得该包罗矩形的Y轴方向的坐标范围(Ymin,Ymax),xa0如此得到能够包围所有二维点数据的包络矩形;步骤2:xa0将上述包络矩形沿X轴方向以及Y轴方向按照固定的长、宽进行格网分解,分解后的小格网长、宽设为上述包络矩形长和宽的1/5至1/100;xa0xa0xa0xa0xa0步骤3:xa0将所有的点坐标分配到每个格网中:即通过坐标计算获得每个二维点(x,y)“所属”的小格网,在每个小格网中存储其所“包含”的二维点的指针;采用下列计算公式即可计算其应该归附的小矩形格网的序列号:设X方向上的格网序号从0开始,沿X正方向;Y方向上的格网序号从0开始,沿Y正方向,则点坐标(x,y)所对应的格网序列号为:X_nxa0=xa0xa0[(x-Xmin)/Lx];xa0xa0Lx:xa0为矩形小格网的X方向上的长度;符号[xa0]表示去余取整运算;Y_n=xa0xa0[(y-Ymin)/Ly];xa0xa0xa0Ly:xa0为矩形小格网的Y方向上的长度;符号[xa0]表示去余取整运算;xa0xa0xa0xa0然后将当前二维点对象的指针保存到该小矩形网格(X_n,Y_n)的变量中(即将该点“归附”到该小矩形格网中),按照这种方法将所有二维点对象归附到其所对应的小格网中;步骤4:然后,设定二维点的排序准则,基于这种准则,对分配到每个小格网内的二维点集数据对象再采用二叉树结构进行组织;设定基于点坐标的排序方法:对于两个二维点,首先按照x坐标大小确定坐标点的“排序”;如果x坐标相同,则进一步按照xa0y坐标的大小确定坐标点的“排序”;如果y坐标也相同xa0,则认为该两点相同(相等);至此完成对大量二维点数据的复合组织,该过程需要进行一次;步骤5:xa0在对现有的大批量二维点数据进行上述的复合组织后,根据任意二维点的坐标xa0(x₀,y₀)进行查询匹对,快速查找到该坐标对应的二维点对象:1)xa0首先,第一次匹配过程,根据其坐标数值(x₀,y₀)计算其对应的格网序号(X_nxa0,Y_n),确定其所在格网:X_nxa0=xa0xa0[(x₀-Xmin)/Lx];xa0xa0xa0xa0xa0Xmin:为包络矩形X方向的坐标最小值xa0xa0xa0Lx:xa0为小矩形格网的X方向上的长度;xa0xa0xa0符号[xa0]表示去余取整运算;Y_n=xa0xa0[(y₀-Ymin)/Ly];xa0xa0xa0xa0Ymin:为包络矩形Y方向的坐标最小值xa0xa0xa0xa0xa0Ly:xa0为矩形小格网的Y方向上的长度;xa0xa0xa0xa0符号[xa0]表示去余取整运算;2)xa0确定格网后,在该小格网中进行第二次匹配过程:通过当前的坐标数值(x₀,y₀),在以二叉数结构存储于该小格网内的二维点集对象中进行比对匹配搜索,快速得到该坐标所对应的实体二维点对象。其中,步骤4中对每个小格网内的二维点按设定排序准则进行二叉树进行组织,采用C++标准模板库中的set容器进行,该set容器实现了二叉树数据结构的组织算法;其中,步骤5的第二次匹配时,直接调用set容器的搜索算法即获得对应的结果。本方法发明首先对所有的二维点数据进行复合结构组织:首先计算大量二维点所在的xa0包络矩形,继而按照固定的长、宽将其分解为规整排列的小矩形格网,继而将所有的二维点数据分别分配到这些小格网中;在此基础上,对分配到每一个格网中的二维点集数据设定能够按照坐标数值进行排序的规则,基于该排序规则,对分配到每一个格网中的二维点集对象再采用二叉树结构进行组织。在上述结构建立成功的基础上,再通过两次匹配即可实现二维坐标的快速查询匹配:当已知某二维坐标数值时,首先快速计算其对应点数据应该存在的格网,继而在该格网中采用二叉树结构组织的二维点集中进行快速查询匹配。整个匹配检索过程可以做到基本与数据量无关。xa0本发明的有益效果如下:该方法发明能够使整个匹配过程与数据量无关,彻底解决基于点坐标的查询匹配问题。正常采用线性结构进行数据匹配,则复杂度为O(n)(整个点集数据规模),也就是说传统方式的比对工作将随着数据量的增加而成线性增加;而采用本方法发明,将待查二维坐标归附到对应的矩形格网中的时间复杂度为c(常量),与整体数据量(数据规模)无关,而进一步在小格网中针对二叉树进行查询,其具有对数复杂度,具有较高的查询效率,在拥有1000个元素的搜索中,其二叉树搜寻动作的平均时间仅为线性时间的1/50,加之分配在每个格网中的数据量仅为整体数据量中的一小部分,故该整个坐标匹配过程中坐标的比对次数以及所消耗时间大大降低。整个过程能够彻底解决二维坐标的点匹配查询问题,为大量二维空间点数据处理彻底解决这一瓶颈问题。
附图说明
图1xa0本发明中数据组织流程的逻辑示意图。图2本发明中二维坐标查询匹配的示意图。
具体实施方式
xa0xa0xa0xa0xa0如图1中a所示的一大批量二维坐标点数据,按照本发明方法对其进行基于坐标的快速匹配查询,首先需要对现存的海量二维点数据进行复合组织,此复合组织结构的基础上再进行坐标的快速匹配。可遵循以下步骤进行:步骤1:xa0xa0xa0对于现有的一批大量二维点数据,首先获取所有二维点数据所在的包络矩形:该包络矩形的两个边分别平行于坐标轴的X轴和Y轴,xa0其中X轴方向的最小值Xmin为所有点数据x坐标的最小值,X轴方向的最大值Xmax为所有点数据x坐标的最大值;同样的方法获得该包络矩形的Y轴方向的坐标范围(Ymin,Ymax),xa0如此得到能够包围所有二维点数据的包络矩形;步骤2:xa0如图1中的C图所示,可以将包络矩形沿X轴方向以及Y轴方向按照固定的长、宽进行格网分解,其小格网的长宽的数值,可以根据二维点的分布密集度以及包罗矩形整体的长宽的数值进行确定,二维点的分布密集,则小格网的长宽的数值可以取小以一些,反之,则取大一些;xa0一般情况下也可以直接取为整个包罗矩形的长宽的1/10(1/5至/100均可以),其最终目的是在计算条件允许以及不过多增加整个算法复杂度的情况下使每个格网中的二维点数量减少到比较少的状态。步骤3:xa0xa0将所有的点坐标分配到每个格网中:即通过空间坐标计算获得每个二维点(x,y)“所属”的小网格,在每个小格网中存储其所“包含”的二维点的指针;采用下列计算公式即可计算其应该归附的小矩形格网的序列号:设X方向上的格网序号从0开始,沿X正方向;Y方向上的格网序号从0开始,沿Y正方向;xa0(其中的方向设定以及开始序号可以根据用户的需要自由设定),则点坐标(x,y)所对应的格网序列号(X_n,Y_n)为:X_nxa0=xa0xa0[(x-Xmin)/Lx];xa0xa0Lx:xa0为小矩形格网的X方向上的长度;符号[xa0]表示去余取整运算;Y_n=xa0xa0[(y-Ymin)/Ly];xa0xa0xa0Ly:xa0为小矩形格网的Y方向上的长度;符号[xa0]表示去余取整运算;xa0xa0xa0xa0然后将当前二维点对象的指针保存到该小矩形网格(X_n,Y_n)的变量中(即将该点“归附”到该小矩形格网中),按照这种方法将所有二维点对象归附到其所对应的小格网中;步骤4:如图1中d图所示,对分配到每个小矩形格网内的二维点集设定排序准则进行二叉树进行组织。鉴于本发明主要用于坐标的匹对,所以需要设定基于点坐标的排序方法。在该排序方法中,由于计算机内部对于点坐标采用实数类型进行存储,故在判断两数相等时,采用相减求差的方法进行。其排序规则可设为:首先按照x坐标大小确定坐标点的“排序”xa0;如果x坐标相同(两者差小于某阈值,可取一个很小的实数(如xa00.0000001)),则进一步按照xa0y坐标的大小确定坐标点的“排序”;如果y坐标也相同(两者差小于某阈值,可取一个很小的实数(如xa00.0000001));xa0则得到该两点相同(等)。根据本排序规则,每个二维坐标点可以“比较大小”,继而可以采用二叉树结构进行组织。在具体实现时可以采用C++标准模板中的set容器进行,该set容器实现了二叉树数据结构的组织算法,可以直接进行数据的二叉树构建以及数据的插入查询等相关功能操作。至此完成对海量二维点数据的复合组织,该过程需要进行一次。步骤5:xa0在对现有的海量二维点数据进行上述的复合组织后,可以根据任意二维点坐标xa0(x₀,y₀)进行查询匹对,快速查找到该坐标对应的二维点对象:1)首先,如图2中的“第一次匹配”过程,根据其坐标数值计算其对应的格网序号(X_nxa0,Y_nxa0):X_nxa0=xa0xa0[(x₀-Xmin)/Lx];xa0xa0xa0xa0xa0Xmin:为包络矩形X方向的坐标最小值xa0xa0xa0Lx:xa0为小矩形格网的X方向上的长度;xa0xa0xa0符号[xa0]表示去余取整运算;Y_n=xa0xa0[(y₀-Ymin)/Ly];xa0xa0xa0xa0Ymin:为包络矩形Y方向的坐标最小值xa0xa0xa0xa0xa0Ly:xa0为小矩形格网的Y方向上的长度;xa0xa0xa0xa0符号[xa0]表示去余取整运算;2)在该格网中,再进行如图2中的“第二次匹配”过程:对该格网中以二叉数结构存储组织的二维点集对象进行比对匹配搜索。如果在步骤4xa0中采用set容器进行二叉树的数据组织实现,则在这里可以直接调用set容器的搜索算法即可获得对应的结果。步骤6xa0算法结束。